Linux Scheduling Through Version 2.5

• 早期的kernel version2.5，是在執行標準的UNIX作業系統演算法。
• Version2.5會移動到恆定順序O(1)的scheduling time：

1. 可中斷且以優先權為基礎。
2. 須由time-sharing和real-time同時支持。
3. Real-time的範圍是0~99，nice value的範圍在100~140。
4. 如果還有時間的話，工作可以在time-slice中執行(active)。
5. 如果沒有時間的話，便要使用其他的time-slice來執行。
6. 所有可執行的工作，會追蹤每一個CPU的runqueue數據架構：
   1-依照優先順序索引
   2-沒有更多的active時，arrays會進行交換。

Linux Scheduling in Version2.6.23+

• 完全公平排程(Completely Fair Scheduler,CFS)。
• Scheduling classes：

1. 每個都擁有具體優先權。
2. 挑選最高優先的任務在最高的scheduling calss。

• 以nice value從-20到+19為基礎，計算quantum。

1. 低數值是高優先權。
2. 如果active工作數量增加的話，target latency也會增加。

• scheduler挑選最低虛擬執行時間的工作決定，來決定下個工作執行。

Windows Scheduling

• Windows使用優先權為基礎且可中斷的scheduling。
• 最高優先權的thread會是下個執行的。
• 使用Dispatch為scheduler。
• Threads為執行到以下三種情況才停止：

1. 遇到blocks
2. 使用time slice
3. 被最高優先權的thread打斷

• Variable class是1-15，real-time class是16-31。
• memory-management thread是最高優先權-0。
• 如果沒有可執行的thread，則會執行閒置中的thread。

Windows Priority Classes

• Win32的API會確定幾個優先calss給哪個行程歸屬。
• 一個thread在給定的優先class類有相對的優先權。
• 優先class與relative priority會結合在一起，並給予數字優先權。
• 在calss中以NORMAL為優先基礎。
• Windows 7加入user-mode scheduling(UMS)：

1. 應用程式會新增與管理threads，而不是依靠kernel。
2. 更多數量的threads，會有更加有效率。
3. UMS scheduling是從programing language libraries來的，像是C++ Concurrent Runtime(ConRT) framework。

Solaris

• 優先基礎的scheduling。
• 6種class可使用：

1. Time sharing(default)(TS)
2. Interactive(IA)
3. Real time(RT)
4. System(SYS)
5. Fair Share(FSS)
6. Fixed priority(FP)

• 讓thread一次在一個class內。
• 每個class都擁有自己的scheduling演算法。
• Time sharing是可移動的multi-level feedback queue。
• Scheduler轉換class-specific priority進入到一個thread的global priority。

1. 最高優先權的thread會是下個執行的工作。
2. 透過RR方法在相同優先權選擇多重threads。

Algorithm Evaluation

• 如何從OS選擇CPU-scheduling algorithm。
• 決定標準然後評估algorithms。
• Deterministic modeling：

1. analytic evaluation是一種方式。
2. 採取特定預定的工作量，並定義工作量的每個algorithm的表現方式。

Deterministic Evaluation

• 計算每個algorithm的最少平均等待時間。
• 簡單且快速，但需要輸入僅適於輸入的準確數字。

Queueing Models

• 描述行程到達的狀況，還有CPU burst、I/O burst的概率。

1. 計算平均吞吐量、採用量和等待時間等。

• 電腦系統會描述服務器的網路、每個正在等待的行程queue。

1. 知道到達速率與服務速率。
2. 計算採用量、平均queue的長度；平均等待時間等。

Little's Formula

• n = 平均queue長度
• w = 在queue內平均等待時間
• 入 = 在queue內的平均到達時間
• Little's law：處於steady的狀態，行程離開queue必須等於行程到達；因此n = 入 x w。

Simulations

• 因為queueing models有限制。
• 使用simulations會更加準確：

1. 是電腦系統的programmed model
2. 設定時間
3. 收集統計演算法的表現

• 如果是大網路、多複雜的實驗，皆可以使用此方法。

Implementation

• 就算是simulation有準確性的限制。
• 執行新的scheduler與測試在實際系統上：

1. 高花費與高風險
2. 環境變化大
3. 但實際做出來的數據、實物也會比較真實。